#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n, n);
        stack<int> st;
        for (int i = 0; i < n; ++i)
        {
            while (!st.empty() && heights[st.top()] >= heights[i])
            {
                right[st.top()] = i;
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }

        int ret = 0;
        for (int i = 0; i < n; ++i)
        {
            ret = max(ret, (right[i] - left[i] - 1) * heights[i]);
        }
        return ret;
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int INF = 0x3f3f3f3f;
        vector<vector<pair<int, int>>> g(n);
        for (auto t : times)
        {
            int x = t[0] - 1, y = t[1] - 1;
            g[x].emplace_back(y, t[2]);
        }
        vector<int> dist(n, INF);
        dist[k - 1] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> Q;
        Q.emplace(0, k - 1);
        while (!Q.empty())
        {
            auto p = Q.top(); Q.pop();
            int time = p.first, u = p.second;
            if (time > dist[u]) continue;
            for (auto& [v, t] : g[u])
            {
                int d = dist[u] + t;
                if (d < dist[v])
                {
                    dist[v] = d;
                    Q.emplace(d, v);
                }
            }
        }
        int ans = *max_element(dist.begin(), dist.end());
        return ans == INF ? -1 : ans;
    }
};